#include "bitree.h"
#include "stdio_ext.h" // include the __fpurge() function

void initTree(BiTree &b)
{
    b = NULL;
}

bool isEmptyTree(BiTree &b)
{
    if(b != NULL)
    {
        return false;
    }else
    {
        return true;
    }
}


int getTreeDepth(BiTree &b)
{
    int left_child_count = 0;
    int right_child_count = 0;
    if(b == NULL)
        return 0;
    left_child_count = getTreeDepth(b->lchild);
    right_child_count = getTreeDepth(b->rchild);
    return left_child_count > right_child_count ? left_child_count + 1 : right_child_count + 1;
}

ElemType getRootData(BiTree &b)
{
    return b->data;
}

void createTree(BiTree &tree)
{
    char input;
    cin>>input;
    if(input == '#')
    {
        tree = NULL;
    }else{
        tree = (BiTree)malloc(sizeof(BiTreeNode));
        if(!tree)
        {
            exit(0);
        }
        tree->data = input;
        createTree(tree->lchild);
        createTree(tree->rchild);
    }
}

void inOrderTraverse(BiTree &tree)
{
    if(tree != NULL)
    {
        inOrderTraverse(tree->lchild);
        cout<<tree->data<<" ";
        inOrderTraverse(tree->rchild);
    }
}

void postOrderTraverse(BiTree &tree)
{
    if(tree != NULL)
    {
        inOrderTraverse(tree->lchild);
        inOrderTraverse(tree->rchild);
        cout<<tree->data<<" ";
    }
}

void preOrderTraverse(BiTree &tree)
{
    if(tree != NULL)
    {
        cout<<tree->data<<" ";
        inOrderTraverse(tree->lchild);
        inOrderTraverse(tree->rchild);
    }
}

bool Stack::isEmpty()
{
    if(s.base == s.top)
        return true;
    else
        return false;
}

void Stack::init()
{
    s.base = (BiTreeNode*)malloc(INIT_STACK_SIZE * sizeof(BiTreeNode));
    if(!s.base)
        exit(0);
    s.top = s.base;
    s.stacksize = INIT_STACK_SIZE;
}

void Stack::display(string comment)
{
    BiTreeNode *temp = s.base;
    cout<<comment<<":";
    for(int i = 1;i <= s.stacksize;i++){
        cout<<(*temp).data<<" ";
        temp++;
    }
    cout<<endl;
}

void Stack::push(BiTreeNode e)
{
    if((s.top - s.base) == s.stacksize){
        s.base = (BiTreeNode*)realloc(s.base,(STACK_INCREMENT + s.stacksize)*sizeof(BiTreeNode));
        if(!s.base)
            return ;
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INCREMENT;
    }
    *(s.top)++ = e; /*为什么要++*/
}

void Stack::pop(BiTreeNode &e)
{
    if(s.base == s.top){
        ;
    }else{
        e = *(--s.top);
    }
}

BiTreeNode *Stack::getTop()
{
    return s.top;
}
